#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // int numTrees(int n)
    // {
    //     vector<int> dp(n + 1, 0);
    //     dp[0] = 1;
    //     dp[1] = 1;
    //     for (int i = 2; i <= n; i++)
    //     {
    //         for (int j = 0; j < i; j++)
    //         {
    //             dp[i] += dp[j] * dp[i - 1 - j];
    //         }
    //     }
    //     return dp[n];
    // }

    int numTrees(int n)
    {
        vector<int> dp(n+1.0);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};

int main()
{
    Solution sol;
    cout << sol.numTrees(4) << endl;
    return 0;
}